For discussion purposes, reference will be made to wireless MAC protocols, however it should be understood that the invention is equally applicable to cabled (ie. wire and optical fibre) and wireless data communications alike.
A protocol generally is a set of agreed conventions (methodology) for handling the exchange of information between communication processing “elements”.
In a wireless medium, the capacity to accommodate multiple users seeking access to the medium must take into account fundamental limitations of bandwidth. For any wireless data communications system there is a finite data carrying capacity, and this capacity must be shared between users on an appropriate basis to satisfy the user's requirements. A number of MAC protocols have been devised for this purpose. Such protocols variously attempt to satisfy the objective of providing users with access to the full medium during times of low load demand, and fair access to the medium during times of high load demand. Furthermore, it may be desirable to guarantee a user the ability to transmit or receive a burst of data on demand regardless of other user load demands.
Usually, users requesting access to a wireless medium will require low reception delays and high throughput. Where wireless data communication services are supplied on a subscription basis, the subscribing users negotiate certain guaranteed performance requirements that have to be met in order for the service provider to retain that subscriber's loyalty.
Known protocols fall broadly within four classes: fixed access, random access, guaranteed access, and hybrid protocols.
The fixed access category includes those MAC protocols where each station is allocated a fixed proportion of the available bandwidth. This category includes time division multiple access (TDMA), frequency division multiple access (FDMA) and code division multiple access (CDMA) protocols. The main problem with fixed access protocols is that they are not flexible enough to efficiently meet the dynamic bandwidth requirements of a local area network (LAN) environment. Additionally, such a protocol could not be operated as the sole access method, as the bandwidth allocation must be established Initially, and reestablished when mobile stations move between wireless areas.
A random access protocol is only statistical in its nature and therefore its performance is never guaranteed. There are many examples of random access protocols including those based on ALOHA, Carrier Sense Multiple Access (CSMA) and collision resolution. Random access protocols can generally be characterised by the following properties. At low aggregate loads a random access protocol usually provides low delay. At high loads, contention will limit throughput and increase delay. Scheduling of transmission by a random access protocol also is difficult due to the lack of guarantees about access to the wireless medium. Similarly, prioritised access to the wireless medium cannot be ensured. ALOHA protocols also tend to ignore collisions, whereas CSMA protocols tend to try and avoid collisions or limit the length of collisions.
Guaranteed Access Protocols, as the name suggests, guarantee access to the medium, and may be achieved using either distributed or centralised control mechanisms. Examples of guaranteed access protocols include polling protocols, token passing protocols and some collision resolution protocols.
Most practical, implementable wireless MAC protocols are designed as a hybrid of two or more protocols from the previously described categories. This allows a wireless MAC protocol to be tailored more easily to provide a range of services given a particular set of wireless physical layer properties. Hybrid protocols are mostly based on the idea of contention on the wireless medium followed by a reservation that holds the wireless medium for a single station without contention.
R-ALOHA is a hybrid protocol that includes elements of random access protocols and guaranteed access protocols. R-ALOHA is based on slotted ALOHA with regular allocation of slots. If a station is successful in transferring a data unit in a slot then it may reserve the same slot in subsequent frames. Reserved access to future slots reduces contention, thus increasing throughput and reducing delay. R-ALOHA has two unsatisfactory aspects. Firstly, it only allows a station to reserve one slot per frame which is too inflexible in a LAN environment. Secondly, a station may keep a slot reserved without restriction, which may result in unfairness and long delays.
A variation of R-ALOHA, Packet Reservation Multiple Access (PRMA), solves these problems for voice traffic. PRMA supports periodic data units (voice traffic) and random data units (data traffic). Only periodic data units can reserve the same slot in future frames. Random data units always use slotted ALOHA access. Problems similar to those experienced for R-ALOHA are avoided in two ways. Firstly, periodic data units are buffered only for a limited period before they are transmitted or discarded, thus reducing the load during congestion. Secondly, stations must give up reservations between, talk spurts. PRMA is thus very dependent on the properties of speech for effective operation. Another example of this physical layer dependence is that the frame rate in PRMA is tied to the speech rate.
In a published paper entitled “A Dynamic packet-switching system for Satellite Broadcast Channels”, (ICC'75, San Francisco, June 1975) the author Binder describes a TDMA based satellite communication scheme where all stations own a channel (or channels) in a frame structure. The frame may have more channels than those owned by stations. All stations receive each transmitted packet via the satellite. Each packet header includes a reservation for the station's queued packets. Stations which do not have a current reservation will have their owned channel used for reservation access. Each station allocates reservation requests on a round-robin basis. A station with new packets to transmit may regain its owned channel by causing a collision. In the next frame all stations will consider the channel reserved by its owner which can then make a reservation request. A master station generates frame markers and transmits the reservation state. This is used by new stations and stations which have lost a packet and hence the reservation sequence.
There is a problem here, however, with packets received with errors. If the packet contained reservations which were processed by other stations, then the receiving station cannot use the reservation scheme for the rest of the frame. This is hard to distinguish from intentional collisions intended to free an owned channel. In addition, a station must receive what it transmits to detect a purposeful collision.
The Motorola ALTAIR™ system uses a reservation protocol with time multiplexed request and data channels in a slotted frame. The start of the frame contains request slots in which user modules (UM) make requests to a central control module (CM) using slotted ALOHA access with an adaptive transmission probability. The end of the frame contains a series of grant slots, which specify the allocation of data slots in the next frame, and a series of management slots. The middle part of the frame contains data slots from the CM to the UMs and allocated data slots from the UMs to the CM. Control information is distributed through blocks at the start and end of a frame with intervening data slots. The mobile station needs to track where it is in this structure and it will lose considerable efficiency if it has a problem receiving a critical block.
An access request is made by competitive ALOHA in the start control block with no feedback until the end of frame control block. Access slots occur in the midst of a potentially long series of user slots. Any failure to track the user slot sequence will affect a station's throughput and the throughput of any other station it collides with. Bandwidth must be consumed to provide guard time between these slots to allow for variation in clock speed between stations.
A more generic reservation protocol than ALTAIR™ was proposed by International Business Machines Corp. for use as the basis of the IEEE 802.11 Standard. It uses a slotted frame with three sections (A, B and C). Each section is preceded by a variable length header containing management information related to the section, including its length. Section A contains the data units from the hub station to the wireless stations, section B contains data units in reserved slots from the wireless stations to the hub station or other wireless stations and section C contains slots used by the wireless stations to send reservations or short data units using a random access protocol. Requests may be for either asynchronous or isochronous bandwidth.
The IBM protocol (disclosed in U.S. Pat. No. 5,384,777, Ahmadi et al, entitled “Adaptive Medium Access Control Scheme for Wireless LAN”) recognises the importance of power conservation by specifying that all necessary control information is carried in the header at the start of each section. The header indicates when data units will be sent to a wireless station in section A and when the wireless station has slots allocated in section B. The wireless station may power-down at other times and during section C if it does not need to send any data units. However, this functionality requires real time interpretation of complex variable length headers, making the IBM protocol an unlikely candidate for high speed operation. Problems in common with the ALTAIR™ system also equally apply.
Recently, the IEEE 802.11 Working Group selected a MAC protocol, Distributed Foundation Wireless MAC (DFWMAC), that will form the basis of all future work. DFWMAC is a very complex protocol with a number of optional facilities that are supposed to allow it to operate with a range of physical layer properties. It also has nodes of operation that allow it to operate with and without the coordination provided by a hub station.
DFWMAC's fundamental mode of operation is known as a distributed coordination function. It uses a CSMA/CA protocol where a mobile station ensures that the channel is clear for a minimum period before transmission. Priority is implemented by ensuring that the sensing occurs for a minimum period depending on the priority level of the data unit. Thus, DFWMAC assumes that the physical layer supports carrier sensing. To avoid the ‘hidden terminal problem’, a mobile station may optionally also use an RTS/CTS type protocol similar to MA/CA to ensure that long data units do not collide with each other. To ensure error free operation, data units are immediately acknowledged at high priority. A disadvantage of carrier sensing is the significant time spent listening to determine that the wireless medium is free. Then the radio unit must be switched from receive to transmit, which takes further significant time.
DFWMAC also includes a second mode of operation, known as a point coordination function, which effectively provides a synchronous data unit service. In this mode, a central hub station divides the bandwidth into a frame consisting of a contention free period and a contention period. During the contention free period, a hub station polls mobile stations on a poling list. The hub station starts a contention free period by sending the first poll at a high priority. The reservation mechanism is entirely unsophisticated: ‘send a message during the contention period’. There are no methods to respond to bursty traffic or to attempt to make efficient use of the medium.
U.S. Pat. No. 4,970,720, Hiroshi Esaki assigned to Toshiba K K, entitled “A Packet Communication Exchanging Apparatus” describes an even simpler CSMA/CA scheme for wired and wireless LANs. Here a station causes a collision to obtain access to the medium by forcing active stations to delay access attempts.